﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace QuityOrdey
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] data = new Int32[] { 2, 2, 5, 4, 7, 8, 5, 6, 1, 1 };//创建一个一维数组
            QuickRun(data, 0, data.Length - 1);//进行快速排序
            for (int i = 0; i < data.Length; i++)
                Console.Write("{0},",data[i]);
            Console.Read();
        }
        /// <summary>
        /// 快速排序算法
        /// </summary>
        /// <param name="data">排序数组</param>
        /// <param name="low">排序上限</param>
        /// <param name="high">排序下限</param>
        static void QuickRun(int[] data, int low, int high)
        {
            //简单设定中间值，并以此为一趟快排的分割点
            //注意这里是一个简单的算法，如果想对这个算法优化的话，可以采取随机的方法来获取分割点
            int middle = data[(low + high) / 2];//快排的轴值选取
            int i = low;//设定移动上标
            int j = high;//设定移动下标
            do//直至分割出两个序列
            {
                while (data[i] < middle && i < high)//扫描中值左边元素
                    i++;
                while (data[j] > middle && j > low)//扫描值右边元素
                    j--;
                if (i <= j)//找到了一对可以交换的值
                {
                    int temp = data[i];
                    data[i] = data[j];
                    data[j] = temp;
                    i++;
                    j--;
                }
            } while (i<=j);
            if (j > low)//递归对比分割点元素都小的那个序列时行快速排序
                QuickRun(data, low, j);
            if (i < high)//递归对比分割点元素都大的那个序列时行快速排序
                QuickRun(data, i, high);
        }
    }
}
